package leetcode.top100;

import java.util.Arrays;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/**
 * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 * <p>
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * <p>
 * 必须原地修改，只允许使用额外常数空间。
 * <p>
 * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 * <p>
 * 1,2,3 → 1,3,2
 * <p>
 * 3,2,1 → 1,2,3
 * <p>
 * 1,1,5 → 1,5,1
 * <p>
 *
 *
 * @date 2019/11/21 0021 上午 11:35
 */
public class Code31_NextPermutation {

    /**
     * 方式1：把数组可能的所有排列给存储起来，利用Set存储，保持字典序。
     * 然后遍历原始数据在当前set中的位置，返回下一个位置即可。处理是set的最后一个情况。
     * 时间复杂度：O(n!)，可能的排列总计有 n! 个。
     * 空间复杂度：O(n)，因为数组将用于存储排列。
     * <p>
     * OJ测试不过，时间复杂度太高。
     */
    public static void nextPermutation(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int[] copy = Arrays.copyOf(nums, nums.length);
        //存储nums的所有排列，按照字典序
        Set<String> set = new TreeSet<>();
        process(copy, 0, set, "");

        StringBuffer sb = new StringBuffer();
        for (int num : nums) {
            sb.append(num);
        }
        Iterator<String> iterator = set.iterator();

        while (iterator.hasNext()) {
            //如果和当前相等，那么再next就是答案
            if (sb.toString().equals(iterator.next())) {
                //如果已经是最后一个，那么就回到第一个
                String res = iterator.hasNext() ? iterator.next() : set.iterator().next();
                for (int i = 0; i < nums.length; i++) {
                    nums[i] = Integer.parseInt(String.valueOf(res.charAt(i)));
                }
                System.out.println(Arrays.toString(nums));
                break;
            }
        }
    }

    private static void process(int[] copy, int index, Set<String> set, String str) {
        if (index == copy.length) {
            set.add(str);
            return;
        }
        for (int i = index; i < copy.length; i++) {
            swap(copy, index, i);
            process(copy, index + 1, set, str + copy[index]);
            swap(copy, index, i);
        }
    }



    /**
     * 方式2：分析见笔记。
     * 例如arr =    -1,0,3,5,4,2,1
     * 由于找下一个字典序，尽量是往数组的后面找，尽量改变数组的最后元素。
     * 所以
     * <p>
     * 1、从数组右侧往左扫描，找到第一个满足arr[i]<arr[i+1]的元素。此时arr[i+1]开始往右都是降序排序。
     * 如上面例子中的3,5。
     * <p>
     * 2、拿3与其右侧的降序的子序列对比，找到其中最小的比3大的元素，如4，与3交换。交换后后半部分是4,5,3,2,1
     * <p>
     * 3、此时4后面的全是降序，由于是要找下一个最小，所以把4后面的全部反转，变成1,2,3,5.
     * <p>
     * 所以最后就是-1,0,4,1,2,3,5
     * <p>
     * 注意要处理最坏情况：如arr = 3,2,1，那么此时从右往左遍历完后，仍没有arr[i]<arr[i+1],就把整个反转。
     *
     * 一个例子完整过程：
     *
     *  3,4,7,6,5,2,1
     *  这个过程中，从右到做找到第一个降序的位置nums[i] < nums[i+1]。 4 < 7
     *  这样保证从i+1 - len-1都是降序的。从len-1往左找到第一个比nums[i]大的，交换这两个数。4与5换。
     *  交换完毕后还是能保证从i+1 - len-1都是降序的。 7 6 4 2 1
     *  nums[i]位置相当于拿到了右侧最小的比nums[i]大的数。3 5,.....
     *  由于i+1到len-1都是降序的，所以整体要翻转成升序。 3,5,1,2,4,6,7
     *
     * @param nums
     */
    public static void nextPermutation1(int[] nums) {

        if (nums == null || nums.length == 0) {
            return;
        }
        int i = nums.length - 2;
        //从右往左找，找到第一个nums[i] < num[i+1]
        //注意这里必须是严格找num[i+1] > nums[i]，等于也不行
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        //找到
        if (i >= 0) {
            //i - 1 的位置，找从i+1到length-1处，最小的比i处大的数，与 i位置交换
            int j = nums.length - 1;
            //注意这里必须是找num[j]大于num[i]，等于也不行，
            //比如{1,5,1}如果是等于，那么1和1换，然后5,1重排，输出1,1,5
            while (j >= 0 && nums[j] <= nums[i]) j--;
            //找到j,交换i和j处的数
            swap(nums, i, j);
            //从i+1到length-1都反转。
            reverse(nums, i + 1);
        } else {
        //没找到
            //i == -1,说明nums是递减的，反转整个数组，也是从i+1到length-1反转。
            reverse(nums, i + 1);
        }

    }

    private static void reverse(int[] nums, int i) {
        int start = i;
        int end = nums.length - 1;
        for (; start < end; start++, end--) {
            swap(nums, start, end);
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {3,4,7,6,5,2,1};
        arr =new int[] {1,2,1};
        nextPermutation1(arr);
        System.out.println(Arrays.toString(arr));
    }
}
